The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(1(1(x1))) → 0(1(2(3(4(1(x1))))))
0(1(1(x1))) → 1(3(1(3(4(0(x1))))))
0(1(1(x1))) → 5(1(3(0(3(1(x1))))))
0(1(4(x1))) → 0(1(3(4(x1))))
0(1(4(x1))) → 1(3(4(2(0(x1)))))
0(1(4(x1))) → 1(5(3(4(0(x1)))))
0(1(4(x1))) → 3(1(3(4(0(x1)))))
0(1(4(x1))) → 1(1(5(3(4(0(x1))))))
0(1(4(x1))) → 1(2(3(4(3(0(x1))))))
0(1(4(x1))) → 1(3(3(4(4(0(x1))))))
0(1(4(x1))) → 1(3(4(5(0(5(x1))))))
0(1(4(x1))) → 3(4(5(5(0(1(x1))))))
1(2(4(x1))) → 1(2(3(4(1(x1)))))
1(2(4(x1))) → 5(3(4(1(2(x1)))))
1(2(4(x1))) → 1(5(2(3(4(3(x1))))))
1(2(4(x1))) → 2(3(3(4(5(1(x1))))))
5(2(1(x1))) → 1(2(2(3(5(4(x1))))))
5(2(1(x1))) → 1(3(2(5(3(4(x1))))))
5(2(4(x1))) → 0(5(2(3(4(x1)))))
5(2(4(x1))) → 5(5(3(4(2(x1)))))
5(2(4(x1))) → 0(3(4(4(5(2(x1))))))
5(2(4(x1))) → 2(2(5(3(4(4(x1))))))
5(2(4(x1))) → 2(3(3(4(5(5(x1))))))
5(2(4(x1))) → 2(3(4(3(5(3(x1))))))
5(2(4(x1))) → 2(5(3(4(0(5(x1))))))
5(2(4(x1))) → 3(1(2(5(3(4(x1))))))
5(2(4(x1))) → 5(2(3(4(0(3(x1))))))
0(0(2(4(x1)))) → 0(4(3(0(2(x1)))))
0(1(1(5(x1)))) → 0(1(3(5(1(2(x1))))))
0(1(2(4(x1)))) → 0(1(2(3(3(4(x1))))))
0(1(4(5(x1)))) → 3(4(0(5(1(x1)))))
0(1(4(5(x1)))) → 3(4(5(3(0(1(x1))))))
0(4(2(1(x1)))) → 0(4(1(2(3(4(x1))))))
0(5(1(4(x1)))) → 0(0(3(5(4(1(x1))))))
1(0(1(4(x1)))) → 3(4(0(1(2(1(x1))))))
1(1(2(4(x1)))) → 1(3(4(1(2(x1)))))
1(2(2(4(x1)))) → 2(2(2(3(4(1(x1))))))
1(2(4(2(x1)))) → 1(2(3(4(2(3(x1))))))
1(5(2(1(x1)))) → 1(0(3(5(1(2(x1))))))
1(5(2(4(x1)))) → 3(2(3(5(1(4(x1))))))
1(5(2(4(x1)))) → 5(2(3(3(1(4(x1))))))
5(0(1(4(x1)))) → 3(4(0(5(3(1(x1))))))
5(2(5(1(x1)))) → 3(5(1(5(2(x1)))))
0(1(1(5(4(x1))))) → 0(0(5(4(1(1(x1))))))
1(0(0(2(4(x1))))) → 0(2(0(4(4(1(x1))))))
1(0(4(2(1(x1))))) → 1(2(3(4(1(0(x1))))))
1(2(5(0(1(x1))))) → 2(3(5(1(0(1(x1))))))
1(5(3(0(4(x1))))) → 5(1(3(4(0(4(x1))))))
5(0(5(2(4(x1))))) → 4(0(0(5(5(2(x1))))))
5(3(2(4(2(x1))))) → 2(1(5(3(4(2(x1))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2.
The certificate found is represented by the following graph.

Start state: 4245
Accept states: [4246, 4247, 4248]
Transitions:
4245→4246[0_1|0]
4245→4247[1_1|0]
4245→4248[5_1|0]
4245→4245[2_1|0, 3_1|0, 4_1|0]
4245→4249[1_1|1]
4245→4253[2_1|1]
4245→4257[3_1|1]
4245→4262[1_1|1]
4245→4267[4_1|1]
4245→4271[2_1|1]
4245→4275[2_1|1]
4245→4280[4_1|1]
4245→4285[5_1|1]
4245→4290[3_1|1]
4245→4295[5_1|1]
4245→4300[4_1|1]
4245→4305[3_1|1]
4245→4310[1_1|1]
4245→4315[3_1|1]
4245→4320[2_1|1]
4249→4250[4_1|1]
4250→4251[3_1|1]
4251→4252[2_1|1]
4252→4247[1_1|1]
4252→4249[1_1|1]
4252→4262[1_1|1]
4252→4310[1_1|1]
4252→4254[1_1|1]
4253→4254[1_1|1]
4254→4255[4_1|1]
4255→4256[3_1|1]
4256→4247[5_1|1]
4256→4249[5_1|1]
4256→4262[5_1|1]
4256→4310[5_1|1]
4256→4254[5_1|1]
4257→4258[4_1|1]
4258→4259[3_1|1]
4259→4260[2_1|1]
4260→4261[5_1|1]
4261→4247[1_1|1]
4261→4249[1_1|1]
4261→4262[1_1|1]
4261→4310[1_1|1]
4261→4254[1_1|1]
4262→4263[5_1|1]
4263→4264[4_1|1]
4264→4265[3_1|1]
4265→4266[3_1|1]
4266→4247[2_1|1]
4266→4249[2_1|1]
4266→4262[2_1|1]
4266→4310[2_1|1]
4266→4254[2_1|1]
4267→4268[3_1|1]
4268→4269[2_1|1]
4269→4270[5_1|1]
4270→4248[0_1|1]
4270→4285[0_1|1]
4270→4295[0_1|1]
4270→4276[0_1|1]
4271→4272[4_1|1]
4272→4273[3_1|1]
4273→4274[5_1|1]
4274→4248[5_1|1]
4274→4285[5_1|1]
4274→4295[5_1|1]
4274→4276[5_1|1]
4275→4276[5_1|1]
4276→4277[4_1|1]
4277→4278[4_1|1]
4278→4279[3_1|1]
4279→4248[0_1|1]
4279→4285[0_1|1]
4279→4295[0_1|1]
4279→4276[0_1|1]
4280→4281[4_1|1]
4281→4282[3_1|1]
4282→4283[5_1|1]
4283→4284[2_1|1]
4284→4248[2_1|1]
4284→4285[2_1|1]
4284→4295[2_1|1]
4284→4276[2_1|1]
4285→4286[5_1|1]
4286→4287[4_1|1]
4287→4288[3_1|1]
4288→4289[3_1|1]
4289→4248[2_1|1]
4289→4285[2_1|1]
4289→4295[2_1|1]
4289→4276[2_1|1]
4290→4291[5_1|1]
4291→4292[3_1|1]
4292→4293[4_1|1]
4293→4294[3_1|1]
4294→4248[2_1|1]
4294→4285[2_1|1]
4294→4295[2_1|1]
4294→4276[2_1|1]
4295→4296[0_1|1]
4296→4297[4_1|1]
4297→4298[3_1|1]
4298→4299[5_1|1]
4299→4248[2_1|1]
4299→4285[2_1|1]
4299→4295[2_1|1]
4299→4276[2_1|1]
4300→4301[3_1|1]
4301→4302[5_1|1]
4302→4303[2_1|1]
4303→4304[1_1|1]
4304→4248[3_1|1]
4304→4285[3_1|1]
4304→4295[3_1|1]
4304→4276[3_1|1]
4305→4306[0_1|1]
4306→4307[4_1|1]
4307→4308[3_1|1]
4308→4309[2_1|1]
4309→4248[5_1|1]
4309→4285[5_1|1]
4309→4295[5_1|1]
4309→4276[5_1|1]
4310→4311[4_1|1]
4311→4312[3_1|1]
4312→4313[2_1|1]
4313→4314[2_1|1]
4314→4247[2_1|1]
4314→4249[2_1|1]
4314→4262[2_1|1]
4314→4310[2_1|1]
4314→4254[2_1|1]
4315→4316[2_1|1]
4316→4317[4_1|1]
4317→4318[3_1|1]
4318→4319[2_1|1]
4319→4247[1_1|1]
4319→4249[1_1|1]
4319→4262[1_1|1]
4319→4310[1_1|1]
4319→4254[1_1|1]
4320→4321[4_1|1]
4321→4322[3_1|1]
4322→4323[5_1|1]
4323→4324[1_1|1]
4323→4325[4_1|2]
4323→4330[4_1|2]
4324→4248[2_1|1]
4324→4285[2_1|1]
4324→4295[2_1|1]
4324→4291[2_1|1]
4325→4326[5_1|2]
4326→4327[3_1|2]
4327→4328[2_1|2]
4328→4329[2_1|2]
4329→4286[1_1|2]
4330→4331[3_1|2]
4331→4332[5_1|2]
4332→4333[2_1|2]
4333→4334[3_1|2]
4334→4286[1_1|2]

(2) BOUNDS(O(1), O(n^1))